// @algorithm @lc id=51 lang=cpp 
// @title n-queens


#define print(...)
// @test(4)=[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
// @test(1)=[["Q"]]
// @test(5)=[["Q....","..Q..","....Q",".Q...","...Q."],["Q....","...Q.",".Q...","....Q","..Q.."],[".Q...","...Q.","Q....","..Q..","....Q"],[".Q...","....Q","..Q..","Q....","...Q."],["..Q..","Q....","...Q.",".Q...","....Q"],["..Q..","....Q",".Q...","...Q.","Q...."],["...Q.","Q....","..Q..","....Q",".Q..."],["...Q.",".Q...","....Q","..Q..","Q...."],["....Q",".Q...","...Q.","Q....","..Q.."],["....Q","..Q..","Q....","...Q.",".Q..."]]
class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> res;
        vector<string> ans;
        string place(n, '.');
        function<void(int,int,int,int)> bt = // mCol,mL,mR 分别代表向下、左下、右下已占bit
        [&](int row, int mCol, int mL, int mR){
            if(row == n){
                print(Mat(ans), "\n")
                res.push_back(ans);
                return;
            }
            for( int mask = ((1<<n)-1) & (~(mCol|mL|mR));
                    mask; mask = mask & (mask-1) ){
                int one = mask&(-mask);
                int j = __builtin_ctz(one);
                place[j] = 'Q';
                ans.push_back(place);
                place[j] = '.';
                bt(row+1, mCol|one, (mL|one)<<1, (mR|one)>>1);
                ans.pop_back();
            }
        };
        print("\nn=", n, "\n")
        bt(0, 0, 0, 0);
        return res;
    }
};